The present invention generally relates to an improved counter and more particularly to an improved 7 to 3 counter for adding seven digital inputs all having a weight X and providing a three-bit sum including a sum bit having a weight X, a first carry bit having a weight 2X, and second carry bit having a weight 4X. The improved 7 to 3 counter of the present invention exhibits a 33% reduction in gate delays and thus a 33% improvement in processing speed over prior art 7 to 3 counters formed solely of full adders.
Multiplication units in computing systems represent one of the bottlenecks in overall system performance because multiplication is an inherently slow operation. This is caused by the fact that, in multiplication, a large number of partial products must be added to produce the final product. For example, 16.times.16 bit multiplication, using a shift-and-add algorithm, requires 16 partial products to be added resulting in 15 carry propagation adder delays to derive the final product.
Different types of counter schemes have been used to speed up the addition of partial products. For example, full adders or 3 to 2 counters can be used to reduce three partial products to two at each stage. An array of 7 to 3 counter circuits will reduce seven partial products to three at each stage. Thus, an efficient implementation of a 7 to 3 counter results in a faster multiplication scheme. One such solution utilizes a 7 to 3 counter which is formed from four full adders. The time to complete such a multiplication may be measured in terms of gate delays with a simple gate such as, for example, a NAND gate, a NOR gate, or inverter, being given a weight of 1 gate delay, a complex gate like an AND-OR-invert gate being given a weight of 1.5 gate delays, and an exclusive OR gate being given a weight of 2 gate delays.
The 7 to 3 counter using four full adders exhibits 12 gate delays. A 16.times.16 bit multiplier formed from such counters requires two arrays of the 7 to 3 counters and one array of full adders. A full adder alone exhibits 4 gate delays. As a result, a 16.times.16 bit multiplier utilizing the aforementioned 7 to 3 counters exhibits an overall gate delay of 28.
Unfortunately, 16.times.16 bit multipliers incorporating 7 to 3 counters formed solely from full adders do not approach the processing speeds offered by other solutions. Hence, there is a need in the art for an improved 7 to 3 counter which exhibits reduced gate delay as compared to the prior art 7 to 3 counters to improve the overall gate delay of a 16.times.16 bit multiplier utilizing such counters. The present invention provides a 7 to 3 counter which, when utilized in a n.times.n bit multiplier, enables the multiplier to surpass most multiplier configurations in terms of gate delays. To that end, a 16.times.16 bit multiplier utilizing the 7 to 3 counter of the present invention exhibits 20 gate delays for a 16.times.16 bit multiplication. The 7 to 3 counter of the present invention provides a 33% reduction in gate delay over the prior art 7 to 3 counter formed solely of full adders.